// pub fn find_max_prime_factor(number: u128) -> u128 {
//     todo!()
// }

// 米勒-拉宾素性测试的实现
fn miller_rabin(n: u128, k: u32) -> bool {
    if n <= 1 || n == 4 {
        return false;
    }
    if n <= 3 {
        return true;
    }

    // 将 n-1 分解为 d * 2^r 的形式
    let mut d = n - 1;
    let mut r = 0;
    while d % 2 == 0 {
        d /= 2;
        r += 1;
    }

    // 进行 k 次测试
    for _ in 0..k {
        // 生成随机底数 a
        let a = 2 + (rand::random::<u128>() % (n - 4));
        let mut x = mod_pow(a, d, n);

        if x == 1 || x == n - 1 {
            continue;
        }

        let mut is_composite = true;
        for _ in 0..r - 1 {
            x = mod_mul(x, x, n);
            if x == n - 1 {
                is_composite = false;
                break;
            }
        }

        if is_composite {
            return false;
        }
    }
    true
}

// 模幂运算
fn mod_pow(mut base: u128, mut exp: u128, modulus: u128) -> u128 {
    if modulus == 1 {
        return 0;
    }
    let mut result = 1;
    base %= modulus;
    while exp > 0 {
        if exp & 1 == 1 {
            result = mod_mul(result, base, modulus);
        }
        base = mod_mul(base, base, modulus);
        exp >>= 1;
    }
    result
}

// 模乘法（避免溢出）
fn mod_mul(a: u128, b: u128, m: u128) -> u128 {
    let mut result = 0;
    let mut a = a % m;
    let mut b = b;
    while b > 0 {
        if b & 1 == 1 {
            result = (result + a) % m;
        }
        a = (a << 1) % m;
        b >>= 1;
    }
    result
}

// 优化后的寻找最大质因数函数
pub fn find_max_prime_factor(mut number: u128) -> u128 {
    if number <= 1 {
        return number;
    }

    // 首先检查输入数是否为质数
    if miller_rabin(number, 20) {
        return number;
    }

    let mut max_prime = 0;

    // 处理2因子
    while number % 2 == 0 {
        max_prime = 2;
        number /= 2;
        // 如果剩余的数是质数，直接返回较大的那个
        if miller_rabin(number, 20) {
            return if number > max_prime { number } else { max_prime };
        }
    }

    let mut i = 3;
    while i <= (number as f64).sqrt() as u128 {
        while number % i == 0 {
            max_prime = i;
            number /= i;
            // 如果剩余的数是质数，直接返回较大的那个
            if miller_rabin(number, 20) {
                return if number > max_prime { number } else { max_prime };
            }
        }
        i += 2;
    }

    if number > 2 {
        max_prime = number;
    }

    max_prime
}

// pub fn find_max_prime_factor(mut number: u128) -> u128 {
//     // 处理特殊情况
//     if number <= 1 {
//         return number;
//     }
    
//     let mut max_prime = 0;
    
//     // 处理所有的2因子
//     while number % 2 == 0 {
//         max_prime = 2;
//         number /= 2;
//     }
    
//     // 从3开始检查奇数因子，直到sqrt(number)
//     let mut i = 3;
//     while i <= (number as f64).sqrt() as u128 {
//         // 当i是因子时，持续除以i
//         while number % i == 0 {
//             max_prime = i;
//             number /= i;
//         }
//         i += 2; // 只检查奇数
//     }
    
//     // 如果最后剩下的number大于2，说明它本身就是一个素数
//     if number > 2 {
//         max_prime = number;
//     }
    
//     max_prime
// }